package 左哥算法.ch19线段树;

import java.util.Arrays;
import java.util.Random;

public class SegmentTree {
    private int N;
    private int[] arr;  //存储原始数组
    private long[] sum;  //存储每个区间的值
    private long[] addTask;  //存储每个区间的增加任务
    private boolean[] update;   //存储区间是否有更新任务。
    private long[] updateTask;  //存储区间的更新任务的值

    public SegmentTree(int[] origin) {
        N = origin.length;
        arr = new int[N + 1];
        for (int i = 0; i < N; i++) {
            arr[i + 1] = origin[i];
        }
        int lenS = (int) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2)) + 1); //
        this.sum = new long[lenS];
        this.addTask = new long[lenS];
        this.update = new boolean[lenS];
        this.updateTask = new long[lenS];
        build(1, 1, N);
    }

    /**
     * 将l-r范围的值填入。target是l-r范围对应的位置。
     */
    public void build(int target, int l, int r) {
        if (l == r) {  //已经到了最底层
            sum[target] = arr[l]; //从原数组中获取
            return;
        }
        int mr = (l + r) >> 1;  //范围的中间值
        build(target << 1, l, mr);        //构建左孩子
        build(target << 1 | 1, mr + 1, r);//构建右孩子
        pushUp(target); //由下向上更新
    }

    public void add(int L, int R, int val) {
        if (L < 1 || R > N || L > R) {
            return;
        }
        add(1, 1, N, L, R, val);
    }

    /**
     * 新增
     * l-r:抛给哪个区间。
     * t：l-r区间对应的位置。
     * L-R：任务区间
     * val：任务增加的值
     */
    public void add(int t, int l, int r, int L, int R, int val) {
        if (L <= l && r <= R) {//能揽下任务
            sum[t] += (r - l + 1) * val;  //给范围每个都加上val
            addTask[t] += val;
            return;
        }
        int mid = (l + r) >> 1;   //孩子的边界，左孩子的右边界（包含），右孩子的左边界（不包含）
        pushDown(t, mid - l + 1, r - mid);  // 将之前的任务下放
        if (L <= mid) {    //任务和左孩子相关
            add(t << 1, l, mid, L, R, val);
        }
        if (R > mid) {     //任务和右孩子相关
            add(t << 1 | 1, mid + 1, r, L, R, val);
        }
        pushUp(t);
    }

    public void update(int L, int R, int val) {
        if (L < 1 || R > N || L > R) {
            return;
        }
        update(1, 1, N, L, R, val);
    }

    /**
     * 更新
     * l-r:抛给哪个区间。
     * t：l-r区间对应的位置。
     * L-R：抛出的任务区间
     * val：任务增加的值
     */
    public void update(int t, int l, int r, int L, int R, int val) {
        if (L <= l && r <= R) {    //能揽下
            update[t] = true;
            updateTask[t] = val;
            sum[t] = (r - l + 1) * val;
            addTask[t] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        pushDown(t, mid - l + 1, r - mid);
        if (L <= mid) {    //任务和左孩子相关，L越过了左孩子的右边界，因为区间是(0,N]，所以右边界是 <=mid
            update(t << 1, l, mid, L, R, val);
        }
        if (R > mid) {     //任务和右孩子相关，R越过了右孩子的左边界，因为区间是(0,N],所以左边界是 >mid
            update(t << 1 | 1, mid + 1, r, L, R, val);
        }
        pushUp(t);
    }

    public long query(int L, int R) {
        if (L < 1 && R > N || L > R) {
            return 0;
        }
        return query(1, 1, N, L, R);
    }

    public long query(int t, int l, int r, int L, int R) {
        if (L <= l && r <= R) {
            return sum[t];
        }
        int mid = (l + r) >> 1;
        pushDown(t, mid - l + 1, r - mid);
        long res = 0;
        if (L <= mid) {    //从左侧区间获取
            res += query(t << 1, l, mid, L, R);
        }
        if (R > mid) {     //从右侧区间获取
            res += query(t << 1 | 1, mid + 1, r, L, R);
        }
        return res;
    }

    /**
     * 向下更新，（任务下发）
     * ln：左孩子区间的个数，rn：右孩子区间的个数。
     */
    public void pushDown(int target, int ln, int rn) {
        int m = target << 1;
        if (update[target]) {    //更新下发给子区间
            update[target] = false;
            if (m < sum.length) {
                update[m] = true;
                updateTask[m] = updateTask[target];
                sum[m] = updateTask[target] * ln;
                addTask[m] = 0;
            }
            if ((m | 1) < sum.length) {
                update[m | 1] = true;
                updateTask[m | 1] = updateTask[target];
                sum[m | 1] = updateTask[target] * rn;
                addTask[m | 1] = 0;
            }
        }
        if (addTask[target] != 0) { //更新任务执行后，一样要下发增加任务。因为有可能是先揽下更新，后揽下增加任务
            if (m < sum.length) {
                addTask[m] += addTask[target];
                sum[m] += addTask[target] * ln;
            }
            if ((m | 1) < sum.length) {
                addTask[m | 1] += addTask[target];
                sum[m | 1] += addTask[target] * rn;
            }
            addTask[target] = 0;
        }
    }

    /**
     * 向上更新
     */
    public void pushUp(int target) {
        int m = target << 1;
        sum[target] = 0;
        if (m < sum.length) {
            sum[target] += sum[m];
        }
        if ((m | 1) < sum.length) {
            sum[target] += sum[m | 1];
        }
    }
}

class Answer {
    int[] arr;

    public Answer(int[] arr) {
        this.arr = new int[arr.length + 1];
        System.arraycopy(arr, 0, this.arr, 1, arr.length);
    }

    public void add(int L, int R, int val) {
        if (L < 1 || R >= arr.length || L > R) {
            return;
        }
        while (L <= R) {
            arr[L++] += val;
        }
    }

    public void update(int L, int R, int val) {
        if (L < 1 || R >= arr.length || L > R) {
            return;
        }
        while (L <= R) {
            arr[L++] = val;
        }
    }

    public long query(int L, int R) {
        if (L < 1 || R >= arr.length || L > R) {
            return 0;
        }
        long res = 0;
        while (L <= R) {
            res += arr[L++];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] num = {1, 3, 5};
        SegmentTree tree = new SegmentTree(num);
        System.out.println(tree.query(1, 3));
        compare();
    }

    public static void compare() {
        int count = 100000;
        Random r = new Random();
        int nRange = 1000;
        int opsRange = 50;
        while (count-- > 0) {
            int n = r.nextInt(nRange) + 1;
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = r.nextInt(nRange);
            }
            Answer answer = new Answer(arr);
            SegmentTree tree = new SegmentTree(arr);
            int ops = r.nextInt(opsRange) + 1;
            StringBuilder str = new StringBuilder(Arrays.toString(arr)).append("\n");
            while (ops-- > 0) {
                int L = r.nextInt(n) + 1;
                int R = r.nextInt(n) + 1;
                int val = r.nextInt(n);
                if (r.nextBoolean()) {
                    str.append("add：");
                    answer.add(L, R, val);
                    tree.add(L, R, val);
                } else {
                    str.append("update：");
                    answer.update(L, R, val);
                    tree.update(L, R, val);
                }
                str.append(L).append(",").append(R).append("：").append(val).append("\t");
            }
            ops = r.nextInt(opsRange) + 1;
            while (ops-- > 0) {
                int L = r.nextInt(n) + 1;
                int R = r.nextInt(n) + 1;
                long ans = answer.query(L, R);
                long query = tree.query(L, R);
                if (ans != query) {
                    System.out.println("----error----");
                    System.out.println("query：" + L + "," + R);
                    System.out.println(str);
                    System.out.println("预期：" + ans);
                    System.out.println("实际：" + query);
                }
            }
        }
        System.out.println("over");
    }
}
